package sort;

import java.util.Random;

/**
 * @Auther: MFM
 * @Date: 2022/3/20 - 03 - 20 - 19:58
 * @version: 1.0
 */

public class mergeSort {
    public void MergeSort(int[] arr){
    if (arr==null){
        return;
    }

        int[] ints = MergeSort(arr, 0, arr.length - 1);

        System.arraycopy(ints,0,arr,0,arr.length);

    }

    public int[] MergeSort(int[] arr1,int start,int end){
        if (start>=end){
            return arr1;
        }

        int index = (start+end)/2;

        int[] arrA = new int[index-start+1];
        int[] arrB = new int[end - index];
        System.arraycopy(arr1,start,arrA,0,index+1);
        System.arraycopy(arr1,index+1,arrB,0,end-index);


        int[] intsA = MergeSort(arrA, 0, arrA.length-1);
        int[] intsB = MergeSort(arrB, 0, arrB.length-1);

        int[] returnInts = MergeSort(intsA, intsB);

        return returnInts;
    }

    public int[] MergeSort(int[] l,int[] r){
        int[] ints = new int[l.length+r.length];

        int index = 0;
        int lIndex = 0;
        int rIndex = 0;

       while (lIndex<l.length || rIndex<r.length){
           if (rIndex == r.length){
               ints[index] = l[lIndex];
               index++;
               lIndex++;
           }else if (lIndex == l.length){
               ints[index] = r[rIndex];
               index++;
               rIndex++;
           }else{
               if (l[lIndex]<r[rIndex]){
                   ints[index] = l[lIndex];
                   index++;
                   lIndex++;
               }else {
                   ints[index] = r[rIndex];
                   index++;
                   rIndex++;
               }
           }
       }

        return ints;
    }

    public static void main(String[] args) {
        /*
         * 测试结果
         * 1000000 排序所用时间为
         * 二路归并 200ms+
         *
         * */
        int[] arr = new int[1000000];
        Random r = new Random();


        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }

        long start = System.currentTimeMillis();

        new mergeSort().MergeSort(arr);

        long end = System.currentTimeMillis();

        System.out.println(end - start);
//        int[] arr = {15,5,2,7,12,6,1,4,3,9,8};
//
//        new mergeSort().MergeSort(arr);
//
//        for (int a : arr
//        ) {
//            System.out.print(a + " ");
//        }
    }
}
